package org.algorithm.biubiu.wheel_1.链表;

import org.algorithm.biubiu.wheel_1.common.ListNode;
import org.junit.Test;

import java.util.Stack;

/**
 * @Date 2022/2/25 13:50
 * @Created by biubiu
 * @Link {https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii}
 */
public class 删除排序链表中的重复元素II {



    @Test
    public  void test(){

        ListNode listNode = deleteDuplicates3(ListNode.build(1, 2, 3, 3, 4, 4, 5));
        System.out.println("listNode = " + listNode);

    }


    public ListNode deleteDuplicates3(ListNode head) {
        if(head == null) return null;
        if(head.next == null) return head;
        if(head.val != head.next.val){
            head.next = deleteDuplicates3(head.next);
            return head;
        }else{
            while(head.next!= null && head.val == head.next.val){
                head = head.next;
            }
            return deleteDuplicates3(head.next);
        }
    }
    public ListNode deleteDuplicates2(ListNode head) {
        if(head==null){
            return head;
        }

        ListNode dummy = new ListNode(head.val-1);
        dummy.next = head;
        head = dummy;

        ListNode pre = dummy;

        while(dummy!=null){
            int curVal = dummy.val;
            Boolean flag =false;

            while(dummy.next!=null && dummy.next.val ==curVal){
                flag = true;
                dummy = dummy.next;
            }

            if(flag){
                pre.next = dummy.next;
                flag = false;
            }else {
                pre = dummy;
            }

            dummy = dummy.next;
        }
        return head.next;
    }


    public ListNode deleteDuplicates(ListNode head) {
        if(head==null){
            return null;
        }
        ListNode dummy =  new ListNode(-1);
        dummy.next = head;
        head = dummy;
        Stack<ListNode> stack = new Stack();
        while(dummy!=null){
            int curVal = dummy.val;
            stack.add(dummy);
            Boolean duplicates = false;

            if(dummy.next!=null){
                while(curVal ==dummy.next.val){
                    duplicates = true;
                    dummy = dummy.next;
                    stack.add(dummy);
                }
            }

            ListNode pre = null;
            if(duplicates){
                while(!stack.isEmpty() && stack.peek().val == curVal){
                    duplicates =false;
                    stack.pop();
                    pre = stack.peek();
                }
            }

            if(pre!=null){
                pre.next = dummy.next;
                pre = null;
            }
            dummy = dummy.next;
        }
        return head.next;

    }
}
